7、完全二叉树的权值

题目 完全二叉树的权值

image-e404b45c

思路分析

image-82d6dc65

分析老半天 找到了一堆性质

发现好像只需要返璞归真

对于每个i 可以通过\(log_2i\)算出它是第几层的（从0开始）

那么只需要用一个map 以层为键 以总和为值 就可以算出每层的总和

image-e821760a

floor 向下取整

log2() 计算\(log_2i\)返回浮点数

代码实现

#include<bits/stdc++.h>
using namespace std;

map<int,int> m;

int main()
{
    int n;cin>>n;
    for(int i=1;i<=n;i++){
      int x;cin>>x;
      int cur=floor(log2(i));
      m[cur]+=x;
    }
    int maxc=-1,maxv=-1;
    for(auto t:m){
      if(t.second>maxv){
          maxv=t.second;
          maxc=t.first;
      }
    }
    cout<<maxc+1;
    return 0;
}

同类题型

视频讲解

⬅️ 6、特别数的和 🏠 00-刷题理模型 ➡️ 8、等差数列